
https://leetcode.cn/problems/three-steps-problem-lcci/

class Solution 
{
public:
    const int MOD = 1e9+7;
    int waysToStep(int n) 
    {
        if(n==1 || n==2) return n;
        if(n==3) return 4;
        vector<int> dp(n+1);
        dp[1]=1;dp[2]=2;dp[3]=4;
        for(int i=4;i<=n;i++)
            dp[i] = ((dp[i-1] + dp[i-2])%MOD + dp[i-3])%MOD;
        return dp[n];
    }
};
